/**
 * 简单HashMap数据结构
 * Api：
 * 1.new：初始化，入参map长度
 * 2.get：根据key获取值
 * 3.getNode：根据key获取整个节点(k,v结构)
 * 4.findNextNumberKey：查找下一个连续自然数，以key为基准查找。key要求是数字类型。
 * 5.putNodes：批量插入节点数据
 * 6.putNode：插入一个节点数据
 * 7.put：存储key与value的值
 * 8.remove：根据key删除值
 * 9.toList：内部数据结构转为无序数组结构
 * 10.toKeyList：内部数据结构转为以key为索引的有序数组结构
 * 11.size：HashMap中存储的元素个数
 */
export default class HashMap<K, V> implements IterableHashMap<K, V> {
    private readonly container: Map<K, V>;

    constructor() {
        this.container = new Map<K, V>();
    }

    public getKey(value: V): K | undefined {
        for (const [key, val] of this.container) {
            if (value === val) {
                return key
            }
        }
        return undefined;
    }

    public get(key: K): V | undefined {
        return this.container.get(key);
    }

    // 查找下一个连续自然数，以key为基准查找。key要求是数字类型。
    public findNextNumberKey(): number {
        const keyArray: K[] = this.sortKey();

        let prior: number = -1;
        for (const key of keyArray) {
            const number: number = <number>key;
            if (prior === -1) {
                prior = number;
            } else if ((number - prior) > 1) {
                return prior + 1;
            }

            prior = number;
        }

        return ++prior;
    }

    private sortKey(): K[] {
        const iterator: IterableIterator<K> = this.container.keys();
        const keyArray: K[] = Array.from(iterator);
        this.sort(<number[]>keyArray, keyArray.length);
        return keyArray;
    }

    private insertSort(array: number[], start: number, end: number): void {
        let sentry: number = 0;
        let j: number = 0;
        for (let i: number = start + 1; i < end; i++) {
            if (array[i] < array[i - 1]) {
                sentry = array[i];
                for (j = i; j > start && array[j - 1] > sentry; j--) {
                    array[j] = array[j - 1];
                }
                array[j] = sentry;
            }
        }
    }

    /* 插入排序 分段排序(类似希尔排序，倍增步长) */
    private sort(array: number[], size: number): void {
        let step: number = 2;
        let sortSize: number = 0;
        while (step <= size) {
            for (let i: number = 0; i < size;) {
                sortSize = i + step;
                if (sortSize > size) sortSize = size;
                this.insertSort(array, i, sortSize);
                i += step;
            }
            if (step == size) break;
            step *= 2;
            if (step > size) step = size;
        }
    }

    public putNodes(nodes: Node<K, V>[]) {
        nodes.forEach((node: Node<K, V>) => {
            this.putNode(node);
        });
    }

    public putNode(node: Node<K, V>) {
        this.put(node.key, node.value);
    }

    public put(key: K, value: V): void {
        this.container.set(key, value);
    }

    public set(key: K, value: V): void {
        this.put(key, value);
    }

    public has(key: K): boolean {
        return this.container.has(key);
    }

    public remove(key: K): boolean {
        return this.container.delete(key);
    }

    public delete(key: K): boolean {
        return this.remove(key);
    }

    // 无序list
    public toList(): Node<K, V>[] {
        const entry: IterableIterator<[K, V]> = this.container.entries();
        const list: Node<K, V>[] = [];
        for (const [key, value] of Array.from(entry)) {
            list.push({ key, value });
        }

        return list;
    }

    // 以key排序，有序list
    public toKeySortList(): Node<K, V>[] {
        const list: Node<K, V>[] = [];
        const keyArray: K[] = this.sortKey();
        for (const key of keyArray) {
            const value: V = <V>this.container.get(key);
            list.push({ key, value })
        }
        return list;
    }

    public size(): number {
        return this.container.size;
    }

    public toObjet(): {} {
        const result: any = {};
        for (const [key, module] of this.container) {
            result[key] = module;
        }
        return result;
    }

    [Symbol.iterator](): Iterator<[K, V]> {
        return this.container[Symbol.iterator]();
    }
}

export interface Node<K, V> {
    key: K,
    value: V
}

interface IterableHashMap<K, V> extends Iterable<[K, V]> {
    get(key: K): V | undefined;

    set(key: K, value: V): void;

    delete(key: K): boolean;

    [Symbol.iterator](): Iterator<[K, V]>;
}

